COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	colour[s85,jmc]		Shapiro program for coloring maps
C00007 ENDMK
C⊗;
colour[s85,jmc]		Shapiro program for coloring maps

Date: Wed, 27 Mar 85 11:04:31 -0200
From: Ehud Shapiro  <Udi%Wisdom.bitnet@WISCVM.ARPA>
Subject: Not the semantics of Concurrent Prolog

I know, I know I should be doing semantics of Concurrent
Prolog, but instead I wrote a Prolog program for map
colouring.  It seems that the program doesn't do any work.
The magic is, as usual, in the combination of unification
and non-determinism.

The program defines the relation colour(Map,Colours),
between a map and a list of colours, which is true if Map
is legally coloured using Colours.

A map is represented using adjacency-lists, where with
each country we associate its colour, and the list of
colours of its neighbours.  If the program is used in
generate-mode, i.e. to colour an uncoloured map, these
colours would be uninstantiated variables.  The program
would then compute all possible colourings.  For example,
the uncoloured map

        ←←←←←←←←←←
        |   a    |
        |←←←←←←←←|
        |b |c |d |
        |←←|←←|←←|
        |e  |f   |
        |←←←|←←←←|

is represented by the term:

map(    [country(a,A,[B,C,D]),
         country(b,B,[A,C,E]),
         country(c,C,[A,B,D,E,F]),
         country(d,D,[A,B,F]),
         country(e,E,[B,C,F]),
         country(f,F,[C,D,E])
        ]
).

And here is the program:

colour←map([Country|Map],Colours) :-
        colour←country(Country,Colours),
        colour←map(Map,Colours).
colour←map([],←Colours).

colour←country(country(←Name,C,AdjacentCs),Colours) :-
        remove(C,Colours,Colours1),
        subset(AdjacentCs,Colours1).

Which uses a couple of utilities:

subset([C|Cs],Colours) :-
        remove(C,Colours,←),
        subset(Cs,Colours).
subset([],←Colours).

remove(C,[C|Cs],Cs).
remove(C,[C1|Cs],[C1|Cs1]) :-
        remove(C,Cs,Cs1).

To test the program, use the following code:

test(Map) :-
        map(Map),
        colours(Colours),
        colour←map(Map,Colours).

colours([red,green,blue,white]).


By the way, the running time of the algorithm is
exponential in the size of the map.

-- Ehud Shapiro

------------------------------

Date: Thu, 28 Mar 85 00:23:12 -0200
From: Ehud Shapiro  <Udi%Wisdom.bitnet@WISCVM.ARPA>
Subject: Addendum

p.s.  An exercise, for all you program-provers out there:

Prove that colour←map(Map,Colours) terminates succesfully,
if Maprepresents a planar graph, and Colours contains four
distinct colours.

Hint: assume that remove/3 and subset/2 are defined
correctly, just concentrate on proving the first three
axioms...